一、啥是树状数组?
树状数组,是支持 单点修改, 前缀和查询的数据结构。
先来看代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
LL tre[N]; int n, m;
int lowbit(int x) {
return x & (-x);
}
void add(int pos, LL val) {
for (int i = pos; i <= n; i += lowbit(i)) {
tre[i] += val;
}
}
LL query(int pos) {
LL ret = 0;
for (int i = pos; i; i &= (i - 1)) {
ret += tre[i];
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), add(i, x);
for (int op, x, k; m--; ) {
scanf("%d%d%d", &op, &x, &k);
if (op == 1) add(x, (LL)k);
else printf("%lld\n", query(k) - query(x - 1));
}
return 0;
}
二、树状数组的tre[i]含义是什么
举例:
| 长度 | ||
|---|---|---|
所以, 表示从第 位开始往前数 个数的和。
那么如果要求第 的数的和,就需要
用几张图来感性认知一下树状数组:
假如要更新 ,则需要更新 。
既然理解了,那就写代码吧!